package leetcode.dynamic;

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
 * 子串
 * 的长度。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * 示例 2：
 * <p>
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * 示例 3：
 * <p>
 * 输入：s = ""
 * 输出：0
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 */
public class LeetCode32_LongestValidParentheses {
    /**
     * dp[i] : i位置结尾的字符串 最长有效长度
     *
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {

        if (s == null || s.length() < 1) {
            return 0;
        }

        int[] dp = new int[s.length()];
        dp[0] = 0;

        char[] arr = s.toCharArray();
        int p;
        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != '(') {
                p = dp[i - 1];
                if (i - p - 1 >= 0) {
                    if (arr[i - p - 1] == '(') {
                        dp[i] = dp[i - 1] + 2 + ((i - p - 2) >= 0 ? dp[i - p - 2] : 0);
                    }
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        LeetCode32_LongestValidParentheses leetCode32_longestValidParentheses = new LeetCode32_LongestValidParentheses();
        int i = leetCode32_longestValidParentheses.longestValidParentheses("(()");
        System.out.println("i = " + i);
    }
}
